package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC678 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     *  lo、hi表示「可能多余的左括号」，一个下界，一个上界，很直观。执行起来就是

        遇到左括号：lo++, hi++
        遇到星号：lo--, hi++（因为星号有三种情况）
        遇到右括号：lo--, hi--
        lo要保持不小于0。（要理解lo的意思，考虑下这个例子(**)(
        如果hi < 0，说明把星号全变成左括号也不够了，False
        最後，如果lo > 0，说明末尾有多余的左括号，False
     * @return:
     */
    class Solution {
        public boolean checkValidString(String s) {
            int unMatchLeftMax = 0, unMatchLeftMin = 0;
            for (char ch : s.toCharArray()) {
                if ('(' == ch) {
                    unMatchLeftMax++;
                    unMatchLeftMin++;
                } else if (')' == ch) {
                    unMatchLeftMax--;
                    if (unMatchLeftMax < 0) return false;//提前返回
                    unMatchLeftMin = Math.max(0, unMatchLeftMin - 1);//最保底，左括号也是得有冗余多的，否则就不合法了，后面不能玩了
                } else {
                    //当前*可以解释为三种情况
                    unMatchLeftMax++;
                    unMatchLeftMin = Math.max(0, unMatchLeftMin - 1);
                }
            }

            return unMatchLeftMin == 0;
        }
    }


    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.checkValidString("(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())"));
        System.out.println(solution.checkValidString("()"));
        System.out.println(solution.checkValidString("(*))"));
    }

    public static void main(String[] args) throws Exception {
        LC678 an = new LC678();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
